package dynamicStudy;

public class DynamicStudy03 {

    /**
     * 有n块石头分别在x轴的0, 1, ..., n-1位置
     * 一只青蛙在石头0，想跳到石头n-1
     * 如果青蛙在第i块石头上，它最多可以向右跳距离ai
     * 问青蛙能否跳到石头n-1上
     *
     * 存在型动态规划问题
     *
     * 用一维数据解决存在性问题
     * @param args
     */
    public static void main(String[] args) {

    }

    public static boolean canJump(int[] A){
        //确定状态
        int n = A.length;
        boolean[] f = new boolean[n];
        //进行初始化
        f[0] = true;

        //进行遍历， 要提前确定转移方程
        for (int i = 1; i < n; i++){
            //先假设调不了
            f[i] = false;
            //枚举看之前可以从那一块石头跳到该石头
            for (int j = 0; j < i; j++){
                //转移方程，能跳到石头j,并且从石头j能跳到石头i
                if (f[j] && j + A[j] >= i){
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n - 1];

    }
}
